#include "rbTree.h"

void rbtree_insert_fixup(RBRoot* root, Node* node)
{
    Node *parent,*tmp;
    //有父亲，且父亲是红色
    while((parent=rb_parent(node))&&rb_is_red(parent))
    {
        Node* uncle,*gparent;
        gparent=rb_parent(parent);//拿到爷爷
        if(parent==gparent->left)
        {
            //情形三
            uncle=gparent->parent;
            if(uncle&&rb_is_red(uncle))
            {
                rb_set_black(parent);
                rb_set_black(uncle);
                rb_set_red(gparent);
                node=gparent;
                continue;
            }
            //情形四
            if(parent->right==node)
            {
                rbtree_left_rotate(root,parent);
                //父亲和node交换
                tmp=parent;
                parent=node;
                node=tmp;
            }
            //情形五
            rbtree_right_rotate(root,gparent);
            rb_set_red(gparent);
            rb_set_black(parent);
        }else{
            //情形三
            uncle = gparent->left;
            //叔叔存在，是红色
            if (uncle && rb_is_red(uncle))
            {
                rb_set_black(parent);
                rb_set_black(uncle);
                rb_set_red(gparent);
                node = gparent;
                continue;
            }
            //情形四
            if (parent->left == node)
            {
                rbtree_right_rotate(root, parent);
                //父亲和node交换
                tmp = parent;
                parent = node;
                node = tmp;
            }
            //情形五
            rbtree_left_rotate(root, gparent);
            rb_set_red(gparent);
            rb_set_black(parent);
        }
    }
    rb_set_black(root->node);
}